package leetcode.editor.cn.q1_300.q;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author qidi
 * @date 2021-11-06 20:58:13
 */
class Q0030_SubstringWithConcatenationOfAllWords {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> res = new ArrayList<>();
            int len = words.length;
            int itemLen = words[0].length();
            if (s.length() < len * itemLen) return res;

            Map<String, Integer> wordMap = new HashMap<>();
            for (int i = 0; i < len; i++) {
                if (!wordMap.containsKey(words[i])) {
                    wordMap.put(words[i], 0);
                }
                wordMap.put(words[i], wordMap.get(words[i]) + 1);
            }

            Map<String, Integer> map = new HashMap<>();
            int size = 0;
            String curStr;
            String preStr;
            for (int i = 0; i < itemLen; i++) {
                int tailJ = i;
                map.clear();
                size = 0;
                for (int j = i; tailJ <= s.length() - itemLen; j += itemLen) {
                    while (size < len && tailJ <= s.length() - itemLen) {
                        size++;
                        curStr = s.substring(tailJ, tailJ + itemLen);
                        tailJ += itemLen;
                        if (!wordMap.containsKey(curStr)) continue;
                        if (!map.containsKey(curStr)) {
                            map.put(curStr, 0);
                        }
                        map.put(curStr, map.get(curStr) + 1);
                    }

                    if (check(wordMap, map)) res.add(j);
                    preStr = s.substring(j, j + itemLen);
                    map.put(preStr, map.get(preStr) != null && map.get(preStr) > 0 ? map.get(preStr) - 1 : 0);
                    size--;
                }
            }
            return res;
        }

        private boolean check(Map<String, Integer> wordsMap, Map<String, Integer> map) {
            for (Map.Entry<String, Integer> entry : wordsMap.entrySet()) {
                if (!map.containsKey(entry.getKey()) || !map.get(entry.getKey()).equals(entry.getValue())) {
                    return false;
                }
            }
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0030_SubstringWithConcatenationOfAllWords().new Solution();
//        System.out.println(solution.findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));
//        System.out.println(solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "word"}));
//        System.out.println(solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"good", "good", "best", "word"}));
//        System.out.println(solution.findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}));
//        System.out.println(solution.findSubstring("aaaaaaaaaaaaaa", new String[]{"aa", "aa"}));
//        System.out.println(solution.findSubstring("abaababbaba", new String[]{"ba", "ab", "ab"}));
//        System.out.println(solution.findSubstring("a", new String[]{"a", "a"}));
//        System.out.println(solution.findSubstring("ababababab", new String[]{"ababa","babab"}));
        String[] arr = new String[5000];
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < 5000; i++) {
            arr[i] = "a";
            s.append("a");
        }
        System.out.println(solution.findSubstring(s.toString(), arr));
    }

}